package org.example;

import java.util.Random;

public class Test1 {
    Random random = new Random();
    public int findKthLargest(int[] nums, int k) {
        return qsort(nums,k,0,nums.length - 1);
    }

    private int qsort(int[] nums, int k, int l, int r) {
        int key = nums[random.nextInt(r - l + 1) + l];
        int left = l - 1, right = r + 1, i = l;
        while (i < right) {
            if (nums[i] < key) swap(nums,++left,i++);
            else if (nums[i] == key) i++;
            else swap(nums,--right,i);
        }
        if (nums.length - right + 1 > k) return qsort(nums,k,right,r);
        else if (nums.length - right + 1 == k) return key;
        else return qsort(nums,k,l,left);
    }

    private void swap(int[] nums, int x, int y) {
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }

    public static void main(String[] args) {
        Test1 test1 = new Test1();
        int[] arr = {3,2,1,5,6,4};
        test1.findKthLargest(arr,2);
        System.out.println(677);
    }
}
